/**
 * 
 */
package org.algos.tree;

import java.util.List;

/**
 * AVL-tree augmented as IntervalTree. IntervalTree holds the root IntervalNode and has methods to
 * insert and search the tree.
 * 
 * Insertions are O(log n)
 * Deletions are O(log n)
 * Search is O(log n)
 * 
 * @author Sreehari
 *
 */
public class IntervalTree<V extends Comparable<V>> {

	//root of the IntervalTree
	private IntervalNode<V> root;
	
	public IntervalNode<V> getRoot() {
		return root;
	}
	
	/**
	 * Method to insert a new interval into the tree.
	 * @param interval
	 */
	public void addInterval(Interval<V> interval){
	
		if(root == null){//If first node
			root = new IntervalNode<V>();
			root.setHeight(0);
			root.setValue(interval);
			root.setMax(interval.getEnd()); //Max value as the highest value in the interval
			
			return;
		}
		
		//assign the newly computed currentRoot to the root
		root = insert(interval, root);
	}
	
	/**
	 * Get the height of given node
	 * @param n
	 * @return
	 */
	private int getHeight(IntervalNode<V> n){
		return ( n != null) ? n.getHeight() : 0;
	}
	
	/**
	 * Method to insert the target interval as a part of the subtree for the given node
	 * After adding the target to the node, the height of the tree is verified at each
	 * node and balanced accordingly
	 * 
	 * @param target
	 * @param node
	 * @return
	 */
	private IntervalNode<V> insert(Interval<V> target, IntervalNode<V> node){
		
		if(node == null){ //We reached the location where we should insert our target into the tree
			node = new IntervalNode<V>();
			node.setValue(target);
			
		}else if(target.getStart().compareTo(node.getValue().getStart()) < 0){
			// if target[low] value is lower than the current node's low value
			// we insert into the left subtree
			
			IntervalNode<V> left = insert(target, node.getLeft());
			node.setLeft(left); //assign the new subtree-root as left child
			
			//if delta of height between left & right subtree is greater than 1
			if( getHeight(node.getLeft()) - getHeight(node.getRight()) >= 2){

				//		if target[low] is less than left node's[low]
				if(target.getStart().compareTo(node.getLeft().getValue().getStart()) < 0){
				
					//rotate current node with it's left child
					node = rotateWithLeftChild( node );
				}else{
					
					//rotate twice for handling left-right rotations 
	                node = doubleWithLeftChild( node );
				}
			}
			
		}else if(target.getStart().compareTo(node.getValue().getStart()) > 0){
			
			//when target[low] is greater than current node's[low]
			//we assign the target into the right subtree
			node.setRight(insert(target, node.getRight()));
			
			//if delta of height between right and left subtree is greater than 1
			if( getHeight(node.getRight()) - getHeight(node.getLeft()) >= 2){
				
				//if target[low] is greater than right child's[low]
				if( target.getStart().compareTo( node.getRight().getValue().getStart()) > 0 ){
					
					//we rotate the current node with it's right child
                    node = rotateWithRightChild( node );
				}else{
					//we rotate twice for right-left rotations
                    node = doubleWithRightChild( node );
				}    
			}
		}
		
		//set the new height as the max height of left or right subtree + 1
		updateHeight(node);
		//node.setHeight(maxHeight(node.getLeft(), node.getRight())+1);
		
		//set the new max as the max of left or right subtree
		updateMax(node);
/*		V mx = max(node.getLeft(), node.getRight());
		if(mx == null){
			mx = node.getValue().getEnd(); //default to the high value of the node
		}
		node.setMax(mx);
*/		
		return node;
	}
	
	/**
	 * left-right rotation
	 * @param node
	 * @return
	 */
	private IntervalNode<V> doubleWithRightChild(IntervalNode<V> node) {
		node.setRight(rotateWithLeftChild( node.getRight() ));
        return rotateWithRightChild( node );
	}

	/**
	 * right-left rotation
	 * @param node
	 * @return
	 */
	private IntervalNode<V> doubleWithLeftChild(IntervalNode<V> node) {
		node.setLeft(rotateWithRightChild( node.getLeft()));
        return rotateWithLeftChild( node );	
    }

	/**
	 * Update height of current node based on the height of
	 * left and right subtree
	 * @param node
	 */
	private void updateHeight(IntervalNode<V> node){
		node.setHeight(maxHeight(node.getLeft(), node.getRight()) + 1);
	}
	
	/**
	 * Update max of the left & right subtree
	 * @param node
	 */
	private void updateMax(IntervalNode<V> node){

		V mx = max(node.getLeft(), node.getRight());
		if(mx == null){
			mx = node.getValue().getEnd();
		}
		node.setMax( mx );
	}
	
	/**
	 * rotate node with right child
	 * @param node
	 * @return
	 */
	private IntervalNode<V> rotateWithRightChild(IntervalNode<V> node) {
		
		IntervalNode<V> rightChild = node.getRight();
		
		node.setRight(rightChild.getLeft());
		rightChild.setLeft(node);
		
		updateHeight(node);
		updateHeight(rightChild);
		
		updateMax(node);
		updateMax(rightChild);
		
		return rightChild;
	}

	/**
	 * rotate node with left child
	 * @param node
	 * @return
	 */
	private IntervalNode<V> rotateWithLeftChild(IntervalNode<V> node) {
		
		IntervalNode<V> leftChild = node.getLeft();
		
		node.setLeft(leftChild.getRight());
		leftChild.setRight(node);
		
		updateHeight(node);
		updateHeight(leftChild);
		
		updateMax(node);
		updateMax(leftChild);
		
		return leftChild;
	}
	
	/**
	 * Max value of the left & right subtree
	 * @param left
	 * @param right
	 * @return
	 */
	private V max(IntervalNode<V> left, IntervalNode<V> right){
		
		if(left != null && right != null){//if both children are not null
			return (left.getMax().compareTo(right.getMax()) >= 0)? left.getMax() : right.getMax();
		}else if(left == null && right != null){//if left tree is empty
			return right.getMax();
		}else if(left != null && right == null){//if right tree is empty
			return left.getMax();
		}
		return null;
	}

	/**
	 * max height among the left & right subtree
	 * @param left
	 * @param right
	 * @return
	 */
	private int maxHeight(IntervalNode<V> left, IntervalNode<V> right){
		int lH = getHeight(left);
		int rH = getHeight(right);
		
		return ( lH < rH) ? rH : lH ;
	}
	
	/**
	 * Remove the given interval from the tree
	 * @param interval
	 */
	public void removeInterval(Interval<V> interval){
		//TODO: removal of the given interval
	}
	
	/**
	 * Search for the given target and the add the matching intervals into
	 * the results
	 * 
	 * @param target
	 * @param results
	 */
	public void search(Interval<V> target, List<Interval<V>> results){
		doSearch(target, root, results);
	}
	
	/**
	 * Search for the intervals matching the value point
	 * 
	 * @param point
	 * @param results
	 */
	public void search(V point, List<Interval<V>> results){
		Interval<V> interval = new Interval<V>(point, point);
		
		search(interval, results);
	}
	
	/**
	 * Search for target interval under the given subtree
	 * 
	 * @param target
	 * @param currentNode
	 * @param results
	 */
	private void doSearch(Interval<V> target, IntervalNode<V> currentNode, 
			List<Interval<V>> results){
		
		if(currentNode == null)//reached the leaf
			return;
		
		//if current node overlaps with the target
		if(currentNode.getValue().overlapWith(target)){
			results.add(currentNode.getValue());
		}
		
		if(currentNode.getLeft() != null
				&& currentNode.getLeft().getMax().compareTo(target.getStart()) >= 0){
			//if max of current node is greater than low of target then there might
			//be an overlap in the left subtree
			
			doSearch(target, currentNode.getLeft(), results);
		}else{
			
			//search for target in the right subtree
			doSearch(target, currentNode.getRight(), results);
		}
	}

}
